/*
实验10-1 分类排序
分数 25
作者 陈越
单位 浙江大学

若有大写字母、小写字母和数字组成的集合存放在一维数组中，请写一个算法使得数组中的字符按大写字母、数字和小写字母的顺序排列。
函数接口定义：

void Partition( ElemSet *a, int n );

函数接口定义中，ElemSet 是用户定义的数据类型，此处定义为
char；序列元素存储在数组 a 中，可以是大写字母、小写字母或数字；另一个参数 n
是数组 a 的长度，其值不超过 105。注意：数组下标从 0 开始。 函数 Partition 需要将
a 中的字符按大写字母、数字和小写字母的顺序排列，并将调整后的序列仍然存在 a
中返回。注意：结果可能不唯一，返回任何一组正确的结果即可。

输入样例：

10
0zA9ayZA30

输出样例：

1

样例说明：

分类后数组 a 有多种可能，函数 Judge 通过比较输入数据 input 和 a 来判定。
例如 [A Z A 0 9 3 0 z a y] 和 [A A Z 0 0 3 9 a y z] 都可以得到输出 1。
只有得到 Judge 输出 1 的结果才是正确的。
*/

#include <stdio.h>
#include <stdlib.h>
typedef char ElemSet; /* 默认元素为字符*/
void Partition(ElemSet *a, int n);
int Judge(ElemSet *input, ElemSet *a, int n); /* 裁判实现，详情略 */
int main(void) {
    ElemSet *a, *input;
    int n, i;

    scanf("%d\n", &n);
    a = (ElemSet *)malloc(sizeof(ElemSet) * n);
    input = (ElemSet *)malloc(sizeof(ElemSet) * n);
    for (i = 0; i < n; i++) {
        scanf("%c", &a[i]);
        input[i] = a[i];
    }
    Partition(a, n);
    printf("%d", Judge(input, a, n)); /* Judge返回 1 表示正确，0 表示错误 */
    return 0;
}
/* 你的代码将被嵌在这里 */

int getOrder(ElemSet c) {
    if (c >= 'A' && c <= 'Z') {
        return 0;
    } else if (c >= '0' && c <= '9') {
        return 1;
    } else {
        return 2;
    }
}

int compare(const void* a, const void* b) {
    return getOrder(*(ElemSet*)a) - getOrder(*(ElemSet*)b);
}

void Partition(ElemSet *a, int n) {
    qsort(a, n, sizeof(ElemSet), compare);
}